package org.example.y24.m12;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Garden {
    public static int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] adj = new ArrayList[n];
        Arrays.setAll(adj, e -> new ArrayList<>());
        for (int[] path : paths) {
            adj[path[0] - 1].add(path[1] - 1);
            adj[path[1] - 1].add(path[0] - 1);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int colors = 0;
            for (int m : adj[i]) {
                if (ans[m] > 0) {
                    colors |= (1 << ans[m]);
                }
            }
            for (int color = 1; color <= 4; color++) {
                if ((colors & (1 << color)) == 0) {
                    ans[i] = color;
                    break;
                }
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        int n1 = 3;
        int[][] paths1 = {{1, 2}, {2, 3}, {3, 1}};
        System.out.println(Arrays.toString(gardenNoAdj(n1, paths1)));

        // Test case 2
        int n2 = 5;
        int[][] paths2 = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 5}};
        System.out.println(Arrays.toString(gardenNoAdj(n2, paths2)));
    }
}
